package org.example.dynamic_planning;

import java.util.Arrays;

public class climb_stairs {
    public static void main(String[] args) {
        //假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
        //每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
        int n = 1;
        int i = climbStairs(n);
        System.out.println(i);
    }

    public static int climbStairs(int n) {
        if (n==1 || n==2) return n;
        int[] arr = new int[n+1];
        Arrays.fill(arr,0);
        arr[1] = 1;
        arr[2] = 2;
        int index = 3;
        while(index <= n){
            arr[index] = arr[index-1] + arr[index-2];
            index++;
        }
        return arr[n];
    }
    //超出时间限制
    public static int climbStairs2(int n) {
        if (n == 1 || n == 2) return n;
        return climbStairs(n-1) + climbStairs(n-2);
    }
}
